package com.otherTest.sort;

import org.junit.Test;

/**
 * 插入排序
 * @author Conceit
 * 在要排序的一组数中，假设前面(n-1)[n>=2] 个数已经是排好顺序的
 * 现在要把第n个数插到前面的有序数中，使得这n个数
 * 也是排好顺序的。如此反复循环，直到全部排好顺序。
 *
 *
 * 从第一个元素开始，该元素可以认为已经被排序
 * 取出下一个元素，在已经排序的元素序列中从后向前扫描
 * 如果该元素（已排序）大于新元素，将该元素移到下一位置
 * 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
 * 将新元素插入到该位置中
 * 重复步骤2
 * @version 1.0, 2017/5/12
 */
public class InsertSort {

    @Test
    public void test1(){

        int []sort={1,6,3,0};
        if(sort.length==0||sort==null){
            System.out.println();
            return;
        }

        int temp=0;
        for(int i=1;i<sort.length;i++){
            //当前index -1
            int j=i-1;
            //当前value
            temp=sort[i];
            //当前index-1 大于等于0 且 当前value小于 当前index-1 的value
            for(;j>=0&&temp<sort[j];j--){
                //将大于temp的值整体后移一个单位
                sort[j+1]=sort[j];
            }
            //
            sort[j+1]=temp;
        }
        //排序完成 进行遍历
        for(int i:sort){
            System.out.println(i);
        }
    }

    //盲写插入排序
    @Test
    public void test2(){
        int []sort={1,6,3,0};
        if(sort.length==0||sort==null){
            System.out.println();
            return;
        }
        //定义局部变量
        int temp=0;
        //从第二个index开始进行遍历
        for(int x=1;x<sort.length;x++){
            //获取之前的index
            int y=x-1;
            //当前index的value
            temp=sort[x];

            //当前的index的value 需要与之前的所有index的value进行比较 若小于之前的value 则进行交换
            for(;y>=0&&temp<sort[y];y--){
                //将当前遍历到value大于外循环的value 值后移一位
                sort[y+1]=sort[y];
            }
            //将当前的外循环的value赋值给
            sort[y+1]=temp;

        }

        for(int z:sort){
            System.out.println(z);
        }
    }


    //插入排序修改
    @Test
    public void test3(){
        int []sort={1,6,3,0};
        if(sort.length==0||sort==null){
            System.out.println();
            return;
        }
        //定义局部变量
        int temp=0;


        for(int x=1;x<sort.length;x++){
            temp=sort[x];
            int y=x-1;
            //每次向前遍历 寻找大于他的value(x)
            for(;y>=0&&temp<sort[y];y--){
                //如果有数据大于他(x) 则将该value(y)向后移动

                sort[y+1]=sort[y];
            }
            //将他放到比他(x)大的值的原位置 如果向前遍历的值小于temp 将temp 赋值给y+1
            sort[y+1]=temp;

        }
        for(int z:sort){
            System.out.println(z);
        }
    }

    //盲写插入排序
    @Test
    public void test4(){
        int []sort={1,6,3,0};
        if(sort.length==0||sort==null){
            System.out.println();
            return;
        }
        //定义局部变量
        int temp=0;

        for(int x=1;x<sort.length;x++){
            int y=x-1;
            temp=sort[x];
            for(;y>=0&&temp<sort[y];y--){
                sort[y+1]=sort[y];
            }
            sort[y+1]=temp;
        }

        for(int z:sort){
            System.out.println(z);
        }
    }

}
